package com.ctrip.demo.leetcode;

/**
 * @author xs.wu
 */
public class LeetCode688 {

    /**
     * 初始化位置
     */
    private static final int[][] DIRS = new int[][]{{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    public static void main(String[] args) {

        System.out.println(knightProbability(3, 2, 0, 0));

    }

    public static double knightProbability(int n, int k, int row, int column) {
        // double[i][j][l]: l次出现在坐标(i,j)次数
        // 空间复杂度优化，每次只需要比较临近位置的值，所以长度只需要设置为2
//        double[][][] dp = new double[n][n][k + 1];
        double[][][] dp = new double[n][n][2];
        // 初始化 double[][][] dp = 1， l = 0 其他情况都是0
        dp[row][column][0] = 1;

        // 转移double[i][j][l] = 1/8 * (dp[i + 1][j + 2][l - 1])
        for (int l = 1; l <= k; l++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 每次都需要重新赋值
                    dp[i][j][l % 2] = 0.0;
                    for (int[] dir : DIRS) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >=0 && x < n && y >= 0 && y < n) {
//                            dp[i][j][l] += dp[x][y][l - 1] * 0.125;
                            dp[i][j][l % 2] += dp[x][y][(l - 1) % 2] * 0.125;
                        }
                    }
                }
            }

        }
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
//                ans += dp[i][j][k];
                ans += dp[i][j][k % 2];
            }
        }

        return ans;
    }
}
